package me.timlong.Tree;


public class SubTree {

    /**
     * 题目描述
     * 输入两棵二叉树A，B，判断B是不是A的子结构。
     * （ps：我们约定空树不是任意一个树的子结构）
     */
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if(null == root1 || null == root2)
            return false;

        // 只有当两个节点的val相同时才进入判断两棵树是否相同
        if(root1.val == root2.val)
            if(isSubTree(root1, root2))
                return true;

        //遍历左右孩子
        return isSubTree(root1.left, root2) || isSubTree(root1.right, root2);
    }

    /**
     * 具体的判断逻辑实现
     *
     *
     *
     * @param root
     * @param subTree
     * @return
     */
    private boolean isSubTree(TreeNode root, TreeNode subTree){
        if(null == subTree)
            return true;
        if(null == root)
            return false;
        if(root.val == subTree.val)
            return isSubTree(root.left, subTree.left) && isSubTree(root.right, subTree.right);
        else
            return false;
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        TreeNode root2 = new TreeNode(2);
        TreeNode root3 = new TreeNode(3);
        TreeNode root4 = new TreeNode(4);
        TreeNode root5 = new TreeNode(5);
        TreeNode root6 = new TreeNode(6);
        TreeNode root7 = new TreeNode(7);

        // 构建树

        root1.left = root2;
        root1.right = root3;
        root2.right = root4;
        root4.left = root5;
        root3.left = root6;
        root3.right = root7;

        // subTree的构建
        TreeNode root2_3 = new TreeNode(3);
        TreeNode root2_6 = new TreeNode(6);
        TreeNode root2_7 = new TreeNode(7);
        root2.left = root2_6;
        root2_6.right = root2_6;
        System.out.println(new SubTree().HasSubtree(root1, root2_6));
    }



}
